A central issue in the design of database systems is the query processing strategy that is employed. Considerable focus has been placed in this area since a poor strategy can adversely effect the performance of the database system. In SQL and similar query processing languages, a query can be expressed in a variety of different representations. Since the transfer of data that usually resides on secondary storage is slower than from main memory, it is imperative that the number of accesses to secondary storage be minimized. Typically, a user writes a query without considering the most efficient manner for realizing the query. This task becomes the responsibility of a query optimizer.
The objective of the query optimizer is to find an execution strategy that causes the result of the query to be produced in the most efficient ("optimal") manner. Optimality is used to denote the best strategy that satisfies a prescribed criteria. Often this criteria is the minimization of a defined metric, such as computational cost. Query optimization is a search process that entails producing a solution space of semantically equivalent expressions that represent the query. The semantically equivalent expressions are generated through the application of rules. The optimizer searches through the solution space finding the optimal solution that best satisfies the defined metric.
The complexity of the query optimizer is dictated by the size of the solution space and by the efficiency of the query optimization procedure. A large solution space increases the complexity of the search space since more expressions need to be considered by the query optimizer. In some situations, a number of redundant expressions are generated that needlessly burdens the optimizer and ultimately increases the execution time for the query. Inefficiencies in the query optimization procedure increase the execution time of a query as well. Accordingly, there is a need to minimize the execution time of a query by constraining the size of the solution space to those expressions that will produce more promising solutions and to utilize efficient search procedures in finding an optimal solution.